package cn.dapeng.window;

import cn.dapeng.utils.BuilderArray;

import java.util.LinkedList;

/**
 * 给定一个整形数组arr和一个整形num
 * 某个arr中的子数组sub，如果想达标，必须满足：
 * sub中最大值减去sub中最小值<=num
 * 返回arr中达标子数组的数量
 */
public class Code02_SumArrayNum {

    /**
     * 对数器 O(N**3)
     * @param arr
     * @param sum
     * @return
     */
    public static int right(int[] arr, int sum) {
        if (arr == null || arr.length == 0 || sum < 0) {
            return 0;
        }
        int N = arr.length;
        int count = 0;
        for (int L = 0; L < N; L++) {
            for (int R = L; R < N; R++) {
                int max = arr[L];
                int min = arr[L];
                for (int i = L + 1; i <= R; i++) {
                    max = Math.max(max, arr[i]);
                    min = Math.min(min, arr[i]);
                }
                if (max - min <= sum) {
                    count++;
                }
            }
        }
        return count;
    }

    public static int getNumOfReachStandard(int[] array, int num) {
        if (array == null || array.length == 0 || num < 0) {
            return 0;
        }

        int length = array.length;
        int answer = 0, r = 0;

        LinkedList<Integer> maxWindow = new LinkedList<>(), minWindow = new LinkedList<>();
        for (int l = 0; l < length; l++) {
            while (r < length) {
                while (!maxWindow.isEmpty() && array[maxWindow.peekLast()] <= array[r]) {
                    maxWindow.pollLast();
                }
                maxWindow.add(r);

                while (!minWindow.isEmpty() && array[minWindow.peekLast()] >= array[r]) {
                    minWindow.pollLast();
                }
                minWindow.add(r);

                if (array[maxWindow.peekFirst()] - array[minWindow.peekFirst()] > num) {
                    break;
                } else {
                    r++;
                }
            }

            answer += r - l;

            if (maxWindow.peekFirst() == l) {
                maxWindow.pollFirst();
            }
            if (minWindow.peekFirst() == l) {
                minWindow.pollFirst();
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        int testTimes = 10000;
        int k = 5;
        for (int i = 0; i < testTimes; i++) {
            int[] array = BuilderArray.builderArray(100, 15);
            if(right(array, k) != getNumOfReachStandard(array, k)) {
                BuilderArray.print(array);
                break;
            }
        }
    }
}
